public class test {
    //leetcode 1171.从链表中删去总和值为零的连续结点
    class Solution {
        public ListNode removeZeroSumSublists(ListNode head) {
            ListNode dummy = new ListNode(0);
            dummy.next = head;
            int sum = 0;// 前缀和
            HashMap<Integer, ListNode> map = new HashMap<>();
            ListNode cur = head;
            map.put(0, dummy);
            while (cur != null) {
                sum += cur.val;
                if (map.containsKey(sum)) {
                    ListNode node = map.get(sum);
                    ListNode temp = node.next;
                    int tempsum = sum;
                    while (temp != cur) {
                        tempsum += temp.val;
                        map.remove(tempsum);
                        temp = temp.next;
                    }
                    node.next = cur.next;
                } else {
                    map.put(sum, cur);
                }
                cur = cur.next;
            }
            return dummy.next;
        }
    }
    //leetcode 328.奇偶链表
    class Solution {
        public ListNode oddEvenList(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            ListNode left = head;
            ListNode right = head.next;
            ListNode righthead = right;
            while (right != null && right.next != null) {
                left.next = right.next;
                left = left.next;
                right.next = left.next;
                right = right.next;
            }
            left.next = righthead;
            return head;
        }
    }
    //leetcode 面试题02.01.移除重复结点
    class Solution {
        // 解法1.使用临时缓冲区HashSet
        public ListNode removeDuplicateNodes1(ListNode head) {
            if (head == null) {
                return null;
            }
            ListNode cur = head;
            HashSet<Integer> set = new HashSet<>();
            set.add(cur.val);
            while (cur.next != null) {
                ListNode curn = cur.next;
                if (set.contains(curn.val)) {
                    cur.next = curn.next;
                } else {
                    set.add(curn.val);
                    cur = cur.next;
                }
            }
            return head;
        }

        // 解法2.不使用临时缓冲区,使用双指针(时间换空间)
        public ListNode removeDuplicateNodes(ListNode head) {
            if (head == null) {
                return null;
            }
            ListNode node = head;// 1
            while (node != null && node.next != null) {
                ListNode cur = node;// 2
                while (cur != null && cur.next != null) {
                    ListNode curn = cur.next;
                    if (curn.val == node.val) {
                        cur.next = curn.next;
                    } else {
                        cur = cur.next;
                    }
                }
                node = node.next;
            }
            return head;
        }
    }
}
